#include <iostream>

namespace me
{
    template <typename K, typename V>
    struct AVLnode
    {
        std::pair<K, V> _data;
        AVLnode* _left;
        AVLnode* _right;
        AVLnode* _parent;
        int _bf; // 平衡因子  

        AVLnode(const std::pair<K, V>& data)
            :_data(data),
            _left(nullptr),
            _right(nullptr),
            _parent(nullptr),
            _bf(0)
        {}
    };

    template <typename K, typename V>
    class avl
    {
        using node = AVLnode<K, V>;
        void destroy(node* root)
        {
            if(root == nullptr) return;
            destroy(root->_left);
            destroy(root->_right);
            delete root;
            root = nullptr;
        }

        node* copy(node* root)
        {
            if(root == nullptr) return nullptr;
            node* newnode = new node(root->_data);

            // 父节点指向左右子树
            newnode->_left = copy(root->_left);
            newnode->_right = copy(root->_right);

            // 左右子树指向父节点
            if(newnode->_left) newnode->_left->_parent = newnode;
            if(newnode->_right) newnode->_right->_parent = newnode;

            return newnode;
        }
    public:
        avl():_root(nullptr) {}
        ~avl()
        {
            destroy(_root);
        }
        avl(const avl& other)
        {
            _root = copy(other);
        }
        avl& operator=(avl other)
        {
            std::swap(_root, other._root);
            return *this;
        }

        bool insert(const std::pair<K, V>& data)
        {
            // 根节点为空，创建新节点，赋值给root
            if(_root == nullptr) {
                node* newnode = new node(data);
                _root = newnode;
                return true;
            }

            // 1. 根节点不为空，找到待插入的位置
            node* cur = _root;
            node* prev = nullptr;
            while(cur) {
                if(data.first < cur->_data.first) {
                    prev = cur;
                    cur = cur->_left;
                }else if(data.first > cur->_data.first) {
                    prev = cur;
                    cur = cur->_right;
                }else{
                    return false;
                }
            }

            // 2.插入，小于父节点，插入到左边，大于插入到右边
            cur = new node(data);
            if(cur->_data.first < prev->_data.first) {
                prev->_left = cur;
            }else {
                prev->_right = cur;
            }            
            cur->_parent = prev;// 让cur指向父亲

            // 3. 更新平衡因子
            while(prev) {
                if(cur == prev->_left) {
                    // 3.1 插入到左子树，平衡因子-1
                    prev->_bf--;
                }else {
                    // 3.2 插入到右子树，平衡因子+1
                    prev->_bf++;
                }

                // 4.bf == 0，更新后高度平衡
                if(prev->_bf == 0) {
                    break;
                }else if(prev->_bf == -1 || prev->_bf == 1) {// bf ==1/-1，原bf == 0，更新后高度变化，需向上更新
                    cur = prev;
                    prev = prev->_parent;
                }else if(prev->_bf == 2 || prev->_bf == -2) {// bf == 2/-2，此时已经不平衡，需要旋转
                    // 旋转
                    if(prev->_bf == -2 && cur->_bf == -1) {
                        // 对prev来说左子树高，对cur来说，也是左子树高，此时进行右单旋
                        // 右单旋：1.cur的右子树，变为prev的左子树 2.prev变为cur的右子树
                        rotateR(prev);
                    }else if(prev->_bf == 2 && cur->_bf == 1) {
                        // 对于prev来说，右子树高，对cur来说，也是右子树高，此时进行左单旋
                        // 左单旋：1.cur的左子树，变为prev的右子树 2.prev变为cur的左子树
                        rotateL(prev);
                    }else if(prev->_bf == -2 && cur->_bf == 1){
                        // 对于cur来说，右子树高；对于prev来说，左子树高
                        // 采取左右双旋：先对cur用一次左单旋，再对prev用一次右单旋
                        rotateLR(prev);
                    }else if(prev->_bf == 2 && cur->_bf == -1) {
                        // 对于cur来说，左子树高；对于prev来说，右子树高
                        // 采用右左双旋：先对cur来一次右单旋，在对prev来一次左单旋
                        rotateRL(prev);
                    }else {
                        assert(false);
                    }
                    break;
                }else {
                    // 不可能走到这里
                    // 如果走到这里，说明平衡因子的更新出了问题
                    assert(false);
                }
            }
            return true;
        }

        node* find(const K& key)
        {
            node* cur = _root;
            while(cur) {
                if(key < cur->_data.first) {
                    cur = cur->_left;
                }else if(key > cur->_data.first) {
                    cur = cur->_right;
                }else{
                    return cur;
                }
            }
            return nullptr;
        }
        
    private:
        // 右单旋
        void rotateR(node* prev)
        {
            //       pprev
            //       prev
            //   cur
            //     curR
            node* cur = prev->_left;
            node* curR = cur->_right;
            node* pprev = prev->_parent;

            //       pprev
            //       cur
            //            prev
            //          curR

            // 1.cur的右子树，变为prev的左子树
            if(curR) curR->_parent = prev; 
            prev->_left = curR;

            // 2. prev变为cur的右子树
            cur->_right = prev;
            prev->_parent = cur;

            // 3.更新cur的指向
            if(prev == _root) {
                _root == cur;
                cur->_parent = nullptr;
            }else {// 如果prev原先不是根，则判断cur应该连接到pprev的左子树还是右子树
                if(prev == pprev->_left) {
                    pprev->_left = cur;
                }else{
                    pprev->_right = cur;
                }
                cur->_parent = pprev;
            }

            // 4.重新更新平衡因子
            prev->_bf = 0;
            cur->_bf = 0;
        }

        // 左单旋
        void rotateL(node* prev)
        {
            //   pprev
            //   prev
            //       cur
            //      curL
            node* cur = prev->_right;
            node* curL = cur->_left;
            node* pprev = prev->_parent;

            //      pprev
            //      cur
            //  prev
            //    curL

            // 1.cur的左子树，成为prev的右子树
            if(curL) curL->_parent = prev;
            prev->_right = curL;

            // 2.prev变为cur的左子树
            cur->_left = prev;
            prev->_parent = cur;

            // 3.更新cur的指向
            if(prev == _root) {
                _root = cur;
                cur->_parent = nullptr;
            }else {
                if(prev == pprev->_left) {
                    pprev->_left = cur;
                }else {
                    pprev->_right = cur;
                }
                cur->_parent = pprev;
            }

            // 4.更新平衡因子
            prev->_bf = 0;
            cur->_bf = 0;
        }

        // 左右双旋
        // 对于cur子树，右子树高
        // 对于prev子树，左子树高
        void rotateLR(node* prev)
        {
            //        pprev
            //        prev
            //     cur
            // curL  curR
            node* cur = prev->_left;
            node* curR = cur->_right;
            int bf = curR->_bf;

            // 先对cur子树来一次左单旋
            rotateL(cur);
            // 再对prev子树，来一次右单旋
            rotateR(prev);

            // 根据curR的平衡因子，来判断平衡因子的更新
            if(bf == -1) {
                // 插入到curR的左子树
                cur->_bf = 0;
                prev->_bf = 1;
                curR->_bf = 0;
            }else if(bf == 1) {
                // 插入到curR的右子树
                cur->_bf = -1;
                prev->_bf = 0;
                curR->_bf = 0;
            }else if(bf == 0) {
                // curR是一个叶子节点
                cur->_bf = 0;
                prev->_bf = 0;
                curR->_bf = 0;
            }else{
                assert(false);
            }
        }

        void rotateRL(node* prev)
        {
            // 右左双旋
            //  pprev
            //  prev
            //      cur
            //    curL
            node* cur = prev->_right;
            node* curL = cur->_left;
            int bf = curL->_bf;

            // 先对cur来一次右单旋
            rotateR(cur);
            // 在对prev来一次左单旋
            rotateL(prev);

            // 更新平衡因子
            if(bf == -1) {
                // 插入到curL的左子树
                cur->_bf = 1;
                prev->_bf = 0;
                curL->_bf = 0;
            }else if(bf == 1){
                // 插入到curL的右子树
                cur->_bf = 0;
                prev->_bf = -1;
                curL->_bf = 0;
            }else if(bf == 0) {
                // curL为插入的节点
                curL->_bf = 0;
                cur->_bf = 0;
                prev->_bf = 0;
            }else {
                assert(false);
            }
        }
    private:        
        node* _root;
    };
}


int main()
{
    return 0;
}